#ifndef LEETCODE_CN_CPP_PROBLEMS_23_H
#define LEETCODE_CN_CPP_PROBLEMS_23_H

#include "utils/list.h"
#include <queue>
#include <vector>

using namespace std;

namespace problem_23
{

class Solution
{
private:
    struct ListNodeGreater
    {
        constexpr bool operator()(const ListNode *a, const ListNode *b)
        {
            return a->val > b->val;
        }
    };

public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        priority_queue<ListNode *, vector<ListNode *>, ListNodeGreater> pqueue;
        for (auto list : lists)
        {
            if (list != nullptr)
            {
                pqueue.push(list);
            }
        }
        ListNode tmpHead(0);
        auto pre = &tmpHead;
        while (!pqueue.empty())
        {
            auto node = pqueue.top();
            pre->next = node;
            pre = pre->next;
            pqueue.pop();
            if (node->next != nullptr)
            {
                pqueue.push(node->next);
            }
        }
        pre->next = nullptr;
        return tmpHead.next;
    }
};

} // namespace problem_23

#endif //LEETCODE_CN_CPP_PROBLEMS_23_H
